#include <windows.h>
#include <malloc.h>
#include <assert.h>
#include "CMemoryManager.h"

#define HEADERSIZE 12
#define FOOTERSIZE 4
#define HEADER_FOOTER_SIZE (HEADERSIZE + FOOTERSIZE)

CMemoryManager* CMemoryManager::mInstance = NULL;

CMemoryManager::CMemoryManager() : mPool(NULL), mEndPoolFooter(NULL), mFreeHead(NULL),
									mTotalPoolSize(0)
{
}

CMemoryManager::~CMemoryManager()
{
	if(mPool)
		free(mPool);
}

CMemoryManager* CMemoryManager::GetInstance()
{
	if(!mInstance)
		mInstance = (CMemoryManager*)malloc(sizeof(CMemoryManager));
	return mInstance;
}

void CMemoryManager::DeleteInstance()
{
	if(mInstance)
	{
		mInstance->~CMemoryManager();
		free(mInstance);
		mInstance = NULL;
	}
}


void CMemoryManager::Init(unsigned int poolSizeInBytes)
{
	mTotalPoolSize = poolSizeInBytes;
	FindFreeMemory = &CMemoryManager::FirstAvailable;

	mPool = (char*)malloc(poolSizeInBytes);

	// Setting up the header
	((Header*)mPool)->size = poolSizeInBytes - HEADER_FOOTER_SIZE;
	((Header*)mPool)->next = ((Header*)mPool);
	((Header*)mPool)->prev = ((Header*)mPool);
	mFreeHead = ((Header*)mPool);

	// Setting up the footer
	// Type casting the pointer after moving it
	// over leaving FOOTERSIZE bytes for the footer
	((Footer*)(mPool + (poolSizeInBytes - FOOTERSIZE)))->size = poolSizeInBytes - HEADER_FOOTER_SIZE;
	mEndPoolFooter = ((Footer*)(mPool + HEADERSIZE + (((Header*)mPool)->size)));

}
char* CMemoryManager::Allocate(unsigned int allocSize)
{
	// Get the free memory slot
	char* memBlock = (char*)((this->*FindFreeMemory)(allocSize));

	if(memBlock == NULL )
		return NULL;

	if(((Header*)memBlock)->next != (Header*)memBlock && ((Header*)memBlock)->size <= allocSize)
	{
		mFreeHead = ((Header*)memBlock)->next;
		((Header*)memBlock)->next->prev = ((Header*)memBlock)->prev;
		((Header*)memBlock)->prev->next = ((Header*)memBlock)->next;
	}
	else if(((Header*)memBlock)->next == (Header*)memBlock && ((Header*)memBlock)->size <= allocSize)
	{
		mFreeHead = NULL;
	}

	// Get the size of the block
	unsigned int size = ((Header*)memBlock)->size;

	if(size > allocSize)
	{
		///////////////////////
		// Free block Header //
		///////////////////////
		// Set the header's new size
		((Header*)memBlock)->size = size - (HEADER_FOOTER_SIZE + allocSize);
		///////////////////////

		// Move to the footer of the free block of memory
		memBlock = memBlock + HEADERSIZE + size;

		///////////////////////////////////////////
		// Footer for the newly allocated memory //
		///////////////////////////////////////////
		// Set the footer to the new size
		((Footer*)memBlock)->size = allocSize;
		((Footer*)memBlock)->size |= (1<<31);
		///////////////////////////////////////////

		// Move back to set up the header for the new block
		memBlock = memBlock - allocSize - HEADERSIZE;

		///////////////////////////////////////////
		// Header for the newly allocated memory //
		///////////////////////////////////////////
		// Set the size and turn on the "used" bit
		((Header*)memBlock)->size = allocSize;
		((Header*)memBlock)->size |= (1<<31);

		// Set next and prev to NULL since it's being used
		((Header*)memBlock)->next = NULL;
		((Header*)memBlock)->prev = NULL;
		///////////////////////////////////////////

		///////////////////////
		// Free block Footer //
		///////////////////////
		// Move over for the new footer
		memBlock = memBlock - FOOTERSIZE;
		// Set the footer size to it's new size
		((Footer*)memBlock)->size = size - (HEADER_FOOTER_SIZE + allocSize);
		///////////////////////
		memBlock = memBlock + HEADER_FOOTER_SIZE;
	}
	else
	{
		// If you don't need to split turn the header and footer on
		((Header*)memBlock)->size |= (1<<31);
		((Footer*)(memBlock + size + HEADERSIZE))->size |= (1<<31);

		memBlock = memBlock + HEADERSIZE;
	}

	// return the location of the new memory block
	return memBlock;
}

CMemoryManager::Header* CMemoryManager::FirstAvailable(unsigned int allocSize)
{
	// If the entry point is NULL there is no free memory
	if(mFreeHead == NULL)
		return NULL;

	Header* testHead = mFreeHead;
	do
	{
		// If there is enough space use this block
		if(testHead->size >= allocSize && testHead->size >= HEADER_FOOTER_SIZE)
			return testHead;
		// If not check the next block
		else
			testHead = testHead->next;

	// If this block is the same as the entry point
	// Kick out of the loop
	} while(testHead != mFreeHead);

	// If no proper block was found return NULL
	return NULL;
}

void CMemoryManager::DeAllocate(char * data)
{
	if(!(((Header*)(data - HEADERSIZE))->size & (1<<31)))
		return;

	// Set the header and footer to unused
	// Save the size that was allocated here
	((Header*)(data - HEADERSIZE))->size &= ~(1<<31);
	unsigned int oldSize = ((Header*)(data - HEADERSIZE))->size;
	((Footer*)(data + oldSize))->size &= ~(1<<31);
	
	// Move the pointer to the header
	data = data - HEADERSIZE;

	/////////////////////////////
	// MERGING CODE
	/////////////////////////////

	// Check to make sure this header isn't at the beginning of the allocated pool
	// And that the Footer(if there is one) is not active
	if(data != mPool && !(((Footer*)(data - FOOTERSIZE))->size & (1<<31)))
	{
		// If both true then MERGE LEFT!

		/////////////////////////////////
		// Left footer to be replaced
		data = data - FOOTERSIZE;
		unsigned int oldLeftBlockSize = ((Footer*)data)->size;

		////////////////////////////////
		// Right footer that will stay
		data = data + HEADER_FOOTER_SIZE + oldSize;
		((Footer*)data)->size = oldLeftBlockSize + oldSize + HEADER_FOOTER_SIZE;

		///////////////////////////////
		// Left header that will stay
		data = data - (oldLeftBlockSize + oldSize + HEADER_FOOTER_SIZE + HEADERSIZE);
		((Header*)data)->size = oldLeftBlockSize + oldSize + HEADER_FOOTER_SIZE;
	}
	else
	{
		if(mFreeHead)
		{
			// If you don't have to merge left
			// then we have to set up this header
			// in the cycling linked list
			((Header*)data)->next = mFreeHead->next;
			mFreeHead->next = ((Header*)data);
			
			((Header*)data)->prev = ((Header*)data)->next->prev;
			((Header*)data)->next->prev = ((Header*)data);
		}
		else
		{
			mFreeHead = (Header*)data;
			mFreeHead->next = mFreeHead;
			mFreeHead->prev = mFreeHead;
		}
	}

	// Check to see if the current free block of memory's footer is
	// at the end of the pool of memory                                       Moving the pointer to the footer then past it to check the header
	// And check the header to the right of this block of memory     typecast   ptr     the allocated size   size of footer
	if((data + ((Header*)data)->size + HEADERSIZE) != (char*)mEndPoolFooter && !(((Header*)(data + ((Header*)data)->size + HEADER_FOOTER_SIZE))->size & (1<<31)))
	{
		// If both of these things are true MERGE RIGHT!
		
		////////////////////////////////////////
		// Left Header that will be revisited
		Header* leftHead = ((Header*)data);
		unsigned int oldBlockSize = leftHead->size;
		
		////////////////////////////////////////
		// Moving to the Right Block's header
		data = data + oldBlockSize + HEADER_FOOTER_SIZE;

		if(mFreeHead == (Header*)data)
			mFreeHead = leftHead;

		if(((Header*)data)->next != ((Header*)data))
		{
			// If this block is connected to other blocks
			// take it out of the loop
			((Header*)data)->prev->next = ((Header*)data)->next;
			((Header*)data)->next->prev = ((Header*)data)->prev;
		}

		unsigned int oldRightBlockSize = ((Header*)data)->size;

		//////////////////////////////////////
		// Move to the Right Block's footer
		data = data + HEADERSIZE + oldRightBlockSize;
		((Footer*)data)->size = oldBlockSize + oldRightBlockSize + HEADER_FOOTER_SIZE;

		// Set the left block's header to the new size
		leftHead->size = ((Footer*)data)->size;
	}
}